package com.springchang.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetoce 283号题目:移动0
 */
public class MoveZeroes_283 {

    //使用俩链表来实现，时间复杂度O(n),空间复杂度O(n)
    public static void moveZeroes(int[] nums) {
        List<Integer> notZeroes = new ArrayList<>();
        List<Integer> zeroes = new ArrayList<>();

        for (int num : nums) {
            if(num == 0) {
                zeroes.add(num);
            } else {
                notZeroes.add(num);
            }
        }

        int index = 0;
        for (Integer notZeroe : notZeroes) {
            nums[index++] = notZeroe;
        }
        for (Integer zeroe : zeroes) {
            nums[index++] = zeroe;
        }
    }

    //双指针实现，时间复杂度是O(n),空间复杂度是O(1)
    public static void moveZeroesByTwoPointer(int[] nums) {
        int left = 0; //左指针，记录已经处理好的数组的左侧小标
        int right = 0; //右指针，记录未处理的数组的下表

        for (right = 0; right < nums.length; right++) {
            if(nums[right] != 0) {
                nums[left++] = nums[right];
            }
        }

        for (int i = left; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,1,0,3,12};
        moveZeroesByTwoPointer(nums);

        System.out.println(String.format("移动过后的数组: %s", Arrays.toString(nums)));
    }
}
